﻿#include <iostream>
#include <string>
using namespace std;'
'
class Solution
{
public:
	string minWindow(string s, string t)
	{
		int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
		int kinds = 0; // 统计有效字符有多少种
		for (auto ch : t)
			if (hash1[ch]++ == 0) kinds++;
		int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
		int minlen = INT_MAX, begin = -1;
		for (int left = 0, right = 0, count = 0; right < s.size(); right++)
		{
			char in = s[right];
			if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
			while (count == kinds) // 判断条件
			{
				if (right - left + 1 < minlen) // 更新结果
				{
					minlen = right - left + 1;
					begin = left;
				}
				char out = s[left++];
				if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
			}
		}
		if (begin == -1) return "";
		else return s.substr(begin, minlen);
	}
};
int search(int* nums, int numsSize, int target)
{
	// 初始化 left 与 right 指针
	int left = 0, right = numsSize - 1;
	// 由于两个指针相交时，当前元素还未判断，因此需要取等号
	while (left <= right)
	{
		// 先找到区间的中间元素
		int mid = left + (right - left) / 2;
		// 分三种情况讨论
		if (nums[mid] == target) return mid;
		else if (nums[mid] > target) right = mid - 1;
		else left = mid + 1;
	}
	// 如果程序⾛到这⾥，说明没有找到⽬标值，返回 -1
	return -1;
}

class Solution
{
public:
	int halveArray(vector<int>& nums)
	{
		priority_queue<double> heap; // 创建⼀个⼤根堆
		double sum = 0.0;
		for (int x : nums) // 把元素都丢进堆中，并求出累加和
		{
			heap.push(x);
			sum += x;
		}
		sum /= 2.0; // 先算出⽬标和
		int count = 0;
		while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
		{
			double t = heap.top() / 2.0;
			heap.pop();
			sum -= t;
			count++;
			heap.push(t);
		}
		return count;
	}
};
class Solution
{
public:
	int halveArray(vector<int>& nums)
	{
		priority_queue<double> heap; // 创建⼀个⼤根堆
		double sum = 0.0;
		for (int x : nums) // 把元素都丢进堆中，并求出累加和
		{
			heap.push(x);
			sum += x;
		}
		sum /= 2.0; // 先算出⽬标和
		int count = 0;
		while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
		{
			double t = heap.top() / 2.0;
			heap.pop();
			sum -= t;
			count++;
			heap.push(t);
		}
		return count;
	}
};
class Solution
{
public:
 vector<int> searchRange(vector<int>& nums, int target) 
 {
 // 处理边界情况
 if(nums.size() == 0) return {-1, -1};
 
 int begin = 0;
 // 1. ⼆分左端点
 int left = 0, right = nums.size() - 1;
 while(left < right)
 {
 int mid = left + (right - left) / 2;
 if(nums[mid] < target) left = mid + 1;
 else right = mid;
 }
 // 判断是否有结果
 if(nums[left] != target) return {-1, -1};
 else begin = left; // 标记⼀下左端点
 // 2. ⼆分右端点
 left = 0, right = nums.size() - 1;
 while(left < right)
 {
 int mid = left + (right - left + 1) / 2; 
 if (nums[mid] <= target) left = mid;
 else right = mid - 1;
 }
 return { begin, right };
 }
};